Data Mining and Knowledge Engineering

E. R. Naganathan ¹, S. Narayanan ², K. Ramesh Kumar ²

Affiliations
1 Department of Computer Applications, Velammal College of Management and Computer Studies, Ambattur-Redhills Road, Chennai – 600066 Tamil Nadu, IN
2 Dept. of Computer Sci. & Engg., Alagappa University, Karaikudi-630003, Tamil Nadu, IN

Abstract

Frequent itemset discovery algorithms have been used to solve various interesting problems over the year.  As data mining techniques are being introduced and widely applied to non-traditional itemsets, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains.  An alternate way of modeling the objects in these data sets, is to use a graph to model the database objects.  Within that model, the problem of finding frequent patterns becomes that of finding subgraphs that occur frequently over the entire set of graphs.   Modeling objects using graphs allows us to represne tarbitrary relations among entities.  In this paper we present a computationally efficient algorithm for finding the ranking of such frequent subgraphs.  The subgraph finding method may follow any one of the existing algorithm.  In order to find out the ranking of subgraphs we present a new method called “graphgain”.  A graphgain is the normalization technique applied at each position for a chosen value of Discounted Cumulative Gain (DCG) of a subgraph.  The DCG alone cannot be used to achieve the performance from one query to the next in the search engine’s algorithm.  To obtain the graphgain an ideal ordering of DCG (IDCG) at each position is to be found out.  For this, a Modified Dicounted Cumulative Gain using “lift” is introduced here and IDCG is also evaluated.  Then the graphgain is evaluated.  Finally, the graphgain for all rules can be averaged to obtain a measure of the average performance of a search engine’s ranking algorithm.  And also the ordering of graphgain will provide the order of evaluation of rules which gives in turn the efficient ranking of subgraph process.

 

Keywords

Graphgain, Lift, Discounted Cumulative Gain.

Full Text

     

E. Ramaraj ¹, K. Ramesh Kumar ²

Affiliations
1 Computer Centre, Alagappa University, Karaikudi-630002, Tamilnadu, IN
2 Department of Computer Science and Engineering, Alagappa University, Karaikudi-630002, Tamilnadu, IN

Abstract

Association rule mining is to extract the interesting correlation and relation between the large volumes of databases. Association rule mining process is divided into two sub problem: The first problem is to find the frequent itemsets from the transaction and second problem is to construct the rule from the mined frequent itemset. Frequent itemsets generation is the prerequisite and most time overwhelming process for association rule mining. Apriori algorithm is the familiar and fundamental algorithm to generate the frequent itemsets from the transaction sets. Till now, Lot of researcher modified the Apriori in various manner like partition approach, Hash function and etc. But most efficient Apriori-like algorithms rely heavily on the minimum support constraints to prune the vast amount of non-candidate itemsets. These algorithms store many unwanted itemsets and transactions. In this paper propose a novel frequent itemsets generation algorithm. The drawback of the HEA, AprioriTId and Apriori overcome by the proposed algorithm. The proposed algorithm is an improved version of High Efficient AprioriTid (HEA) algorithm. The proposed algorithm is using the two theorems which are proposed in this paper. The proposed algorithm is tested with the synthetic retail dataset. It performed well at low supports. The experimental reports also show that proposed algorithm on an outset is faster than HEA, AprioriTID and Apriori.

Keywords

Data Mining, Association Rule Mining, Frequent Itemsets, Transaction Reduction.

Full Text